Common Mistakes & Debugging Tips

Understanding common pitfalls is key to writing robust traversal code.

Forgetting to use a visited set is the most common error, often leading to infinite loops in graphs with cycles.
Using the wrong data structure (queue vs. stack) will produce a valid traversal, but it won't be the one you intended (BFS vs. DFS).
Applying BFS for shortest paths on weighted graphs will give incorrect results. BFS only works when all edge weights are uniform (e.g., 1).
Debugging Tip: Print the contents of your queue/stack at each step, and log which node is being visited. This makes the algorithm's behavior transparent.

Debugging Checklist
Mistake	Symptom	Diagnostic
No `visited` set	Infinite loop, repeated node visits	Log every node visit; check for duplicates
Wrong Data Structure	Incorrect traversal order	Log queue/stack state; assert FIFO/LIFO
BFS on Weighted Graph	Wrong shortest path distances	Use Dijkstra's algorithm instead

Debugging Examples: Three common mistakes (use the controls)

# Buggy BFS: Can cause infinite loop (missing visited)
def buggy_bfs(G, s):
    q = deque([s])
    while q:
        u = q.popleft()
        for w in G[u]:
            # Mistake: No check if 'w' was already seen!
            q.append(w)



                        # Fix: Track visited nodes
def bfs(G, s):
    visited = set([s])
    q = deque([s])
    while q:
        u = q.popleft()
        for w in G[u]:
            if w not in visited:
                visited.add(w)
                q.append(w)


                        
                        # Buggy traversal: Using list as a stack but intended BFS
def intended_bfs(G, s):
    q = [s]   # using a stack-like list
    while q:
        u = q.pop()           # Mistake: pop() -> LIFO, this yields DFS order


                        # Fix: Use deque for FIFO behavior (BFS)
from collections import deque
def bfs(G, s):
    q = deque([s])
    while q:
        u = q.popleft()   # FIFO: correct for BFS


                        
                        # Buggy shortest path: BFS used on weighted graph
def shortest_paths(G, s):
    dist = {s: 0}
    q = deque([s])
    while q:
        u = q.popleft()
        for v, w in G[u]:
                        # Mistake: treating each edge as unit-cost
            if v not in dist:
                dist[v] = dist[u] + 1


                        # Fix: Use Dijkstra for non-uniform positive weights
import heapq
def dijkstra(G, s):
    dist = {s: 0}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')): continue
        for v, w in G[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))


                    
                        Initial state
                        Step: 0/0